package Sort;
  //归并排序+插入排序
public class MergeInsertionSort {
      public static void insertion(int[] a, int left, int right) {
          for (int low = left + 1; low <= right; low++) {
              int t = a[low];
              int i = low - 1;
              while (i >= left && t < a[i]){
                  a[i + 1] = a[i];
                  i--;
              }
              if(i != low - 1){
                  a[i+1] = t;
              }
          }
      }
      //合并有序数组
      public static void merge(int[] a1,int i ,int iEnd, int j, int jEnd, int[] a2){
          int k = i;
          while (i <= iEnd && j <= jEnd ){
              if(a1[i] < a1[j]){
                  a2[k] = a1[i];
                  i++;
              }else{
                  a2[k] = a1[j];
                  j++;
              }
              k++;
          }
          if(i > iEnd){
              System.arraycopy(a1,j,a2,k,jEnd - j + 1);
          }
          if(j > jEnd){
              System.arraycopy(a1,i,a2,k,iEnd - i + 1);
          }
      }
      public static void sort(int[] a1){
          int[] a2 = new int[a1.length];
          split(a1,0,a1.length - 1,a2);
      }
      private static void split(int[] a1, int left, int right, int[] a2){
          //2.治
          if(left - right == 32){
              //插入排序
              insertion(a1,left,right);
              return;
          }
          //1.分
          int m = (left + right) >>> 1;
          split(a1,left,m,a2);
          split(a1,m+1,right,a2);
          //3.合
          merge(a1,left,m,m+1,right,a2);
          System.arraycopy(a2,left,a1,left,right - left +1);
      }

  }
